10417. Заблокированный рекламный щит II

Корова Бесси привыкла к красивому виду из своего сарая: через дорогу стояли два щита, рекламирующих восхитительный корм для коров. К сожалению, один из этих рекламных щитов недавно был заменен, и теперь на нем рекламируются “Газонокосилки фермера Ларри”. Бесси не является поклонницей газонокосилок, так как их единственная цель – срезать траву на ее поле, которую она считает довольно вкусной (если Вы еще не заметили, то большая часть мыслительного процесса Бесси вращается вокруг еды).

К счастью, оставшийся рекламный щит кормов для коров расположен перед рекламным щитом газонокосилки, потенциально скрывая его.

Бесси, решив полностью убрать из поля зрения агрессивный рекламный щит газонокосилки, вынашивает рискованный план. Она собирается украсть большой прямоугольный брезент из сарая и улизнуть поздно ночью, чтобы прикрыть оставшуюся часть рекламного щита газонокосилки, чтобы больше не видеть какую-либо его часть.

Зная расположение двух рекламных щитов, помогите Бесси определить минимальную площадь необходимого брезента. Поскольку единственный брезент, доступный в сарае, имеет прямоугольную форму, Бесси замечает, что ей, вероятно, потребуется брезент, площадь которого немного больше, чем открытая площадь рекламного щита газонокосилки, как показано в примере ниже. Брезент можно располагать только так, чтобы его стороны были параллельны сторонам других рекламных щитов (то есть его нельзя “наклонять”).

Вход. Первая строка содержит четыре целых числа: x₁ y₁ x₂ y₂, где (x₁, y₁) и (x₂, y₂) – координаты нижнего левого и верхнего правого углов рекламного щита газонокосилки в двумерном поле зрения Бесси. Следующая строка содержит еще четыре целых числа, аналогичным образом определяющих левый нижний и правый верхний углы рекламного щита кормов для коров. Рекламный щит кормов может закрывать все, некоторые или вообще не закрывать рекламные щиты газонокосилки. Все координаты находятся в диапазоне от -1000 до +1000.

Выход. Выведите минимальную площадь брезента, которую Бесси должна использовать для покрытия части рекламного щита газонокосилки, чтобы он стал полностью закрытым.

Пример входа	Пример выхода
2 1 7 4 5 -1 10 3	15

РЕШЕНИЕ

геометрия

Анализ алгоритма

Задача состоит в нахождении прямоугольника наименьшей площади, выровненного по осям координат, который покрывает оставшуюся часть прямоугольника газонокосилки, частично перекрытого другим прямоугольником, обозначающим корм для коров.

Рссмотрим три случая:

· Если все четыре угла прямоугольника покрыты, то он должен быть полностью покрыт, и в этом случае площадь равна нулю.

· Если покрыты два угла прямоугольника, то мы можем удалить только пересечение площадей двух прямоугольников, а оставшуюся часть площади можно точно покрыть.

· Если покрыто менее двух углов прямоугольника, то следует покрыть весь прямоугольник, так как одна из пар противоположных углов останется непокрытой.

Точка (x, y) принадлежит прямоугольнику (x₁, y₁) – (x₂, y₂), для которого x₁ ≤ x₂ и y₁ ≤ y₂, если выполняются следующие неравенства:

· x₁ ≤ x ≤ x₂;

· y₁ ≤ y ≤ y₂;

Пусть два прямоугольника заданы координатами своих противоположных углов:

· (a₁, b₁) – (a₂, b₂), a₁ < a₂, b₁ < b₂;

· (a₃, b₃) – (a₄, b₄), a₃ < a₄, b₃ < b₄;

Их пересечением будет прямоугольник. Найдем координаты вершин его противоположных углов:

· x_L = max(a₁, a₃), y_L = max(b₁, b₃);

· x_R = min(a₂, a₄), y_R = min(b₂, b₄);

Пример

Рекламный щит кормов для коров частично перекрывает правый нижний угол рекламного щита газонокосилки. Тем не менее, Бесси все еще должна использовать брезент, размер которого соответствует размеру всего рекламного щита газонокосилки.

Реализация алгоритма

Функция covered проверяет, принадлежит ли точка (x, y) прямоугольнику (x₁, y₁) – (x₂, y₂).

int covered(int x, int y, int x1, int y1, int x2, int y2)

{

return x1 <= x && x <= x2 && y1 <= y && y <= y2;

}

Основная часть программы. Читаем входные данные – координаты рекламных щитов.

scanf("%d %d %d %d", &a1, &b1, &a2, &b2);

scanf("%d %d %d %d", &a3, &b3, &a4, &b4);

В переменной cornerCover подсчитываем количество вершин щита с газонокосилками, которые покрываются щитом с кормами.

cornerCover = 0;

if (covered(a1, b1, a3, b3, a4, b4)) cornerCover++;

if (covered(a1, b2, a3, b3, a4, b4)) cornerCover++;

if (covered(a2, b1, a3, b3, a4, b4)) cornerCover++;

if (covered(a2, b2, a3, b3, a4, b4)) cornerCover++;

Если у прямоугольника покрыты меньше двух углов, то брезентом покрываем его весь.

if (cornerCover < 2)

printf("%d\n", (a2 - a1) * (b2 - b1));

Если у прямоугольника покрыты все 4 угла, то покрыт и весь прямоугольник.

else if (cornerCover == 4)

printf("0\n");

else

{

Вычисляем пересечение прямоугольников. В пересечении получаем прямоугольник (x_L, y_L) – (x_R, y_R).

int xL = max(a1, a3);

int xR = min(a2, a4);

int yL = max(b1, b3);

int yR = min(b2, b4);

Брезентом покрываем часть щита с газонокосилками, которая не закрыта щитом с кормами. Для этого вычитаем из площади щита с газонокосилками (a₂ – a₁) * (b₂ – b₁) площадь пересечения щитов (x_R – x_L) * (y_R – y_L).

res = (a2 - a1) * (b2 - b1) - (xR - xL) * (yR - yL);

Выводим ответ.

printf("%d\n", res);

}